//
// Created by liushuai on 2021/1/21.
//

#include "smallestK.h"

int Partition(vector<int>& array,int left,int right){
    int l = left;
    int r = right;
    int privot = array[r];
    while(l!=r){
        while(l<r&&array[l]<=privot)
            l++;
        if(l<r){
            array[r] = array[l];
            r--;
        }
        while (l<r&&array[r]>=privot)
            r--;
        if(l<r){
            array[l] = array[r];
            l++;
        }
    }
    array[l] = privot;
    return l;
}

vector<int> smallestK(vector<int> &arr, int k) {
    vector<int> result;
    if(k == 0)
        return result;
    int left = 0;
    int right = arr.size()-1;
    int index = Partition(arr,left,right);
    while (index!=k-1){
        if(index>k-1){
            right = index-1;
            index = Partition(arr,left,right);
        }else{
            left = index+1;
            index = Partition(arr,left,right);
        }
    }
    result.insert(result.begin(),arr.begin(),arr.begin()+index+1);
    return result;
}